package main

import (
	"fmt"
)

// 树定义：无向无环图即为一棵树，任意一个节点可以作为根节点
func main() {
	adj := make([][]int, 8)
	//u, v := 0, 0
	//for {
	//	n, err := fmt.Scanln(&u, &v)
	//	if err == io.EOF {
	//		return
	//	}
	//	if n == 0 {
	//		break
	//	}
	//	adj[u] = append(adj[u], v)
	//	adj[v] = append(adj[v], u)
	//}
	for _, uv := range [][3]int{
		{0, 1, 1},
		{0, 2, 4},
		{0, 3, 7},
		{3, 4, 1},
		{3, 5, 3},
		{1, 7, 1},
		{7, 6, 2},
	} {
		u, v := uv[0], uv[1]
		adj[u] = append(adj[u], v)
		adj[v] = append(adj[v], u)
	}
	fmt.Println(adj)
	l, s, t, p := diameterBy2Dfs(adj)
	fmt.Printf("直径：%d，起点：%d，终点：%d\n", l, s, t)
	var walk []int
	for j := p[t]; j != -1; j = p[j] {
		walk = append(walk, j)
	}
	for i, j := 0, len(walk)-1; i < j; {
		walk[i], walk[j] = walk[j], walk[i]
		i++
		j--
	}
	walk = append(walk, t)
	fmt.Println("路径点：", walk)
	l, c, p := diameterByTreeDp(adj)
	fmt.Printf("直径：%d，起点：%d，锚点：%d，终点：%d\n", l, p[0], c, p[len(p)-1])
	fmt.Println("路径：", p)
}

func diameterBy2Dfs(adj [][]int) (l int, s, t int, p []int) {
	var dfs func(u, fa int)
	d := make([]int, len(adj))
	p = make([]int, len(adj))
	for i := range p {
		p[i] = -1
	}
	c := 0
	dfs = func(u, fa int) {
		for _, v := range adj[u] {
			if v == fa {
				continue
			}
			d[v] = d[u] + 1
			p[v] = u
			if d[v] > d[c] {
				c = v
			}
			dfs(v, u)
		}
	}
	p[0] = -1
	dfs(0, 0) // adj里面一定要有节点0
	s = c
	d[c] = 0
	p[c] = -1
	dfs(c, c)
	t = c
	l = d[c]
	return
}

func diameterByTreeDp(adj [][]int) (l int, c int, p []int) {
	n := len(adj)
	d1, d2 := make([]int, n), make([]int, n)
	p1, p2 := make([]int, n), make([]int, n)
	for i := 0; i < n; i++ {
		p1[i] = -1
		p2[i] = -1
	}
	c = -1
	var dfs func(u, fa int)
	dfs = func(u, fa int) {
		d1[u], d2[u] = 0, 0
		for _, v := range adj[u] {
			if v == fa {
				continue
			}
			dfs(v, u)
			w := d1[v] + 1
			if w > d1[u] {
				d1[u], d2[u] = w, d1[u]
				p1[u], p2[u] = v, p1[u]
			} else if w > d2[u] {
				d2[u] = w
				p2[u] = v
			}
		}
		if d1[u]+d2[u] > l {
			l = d1[u] + d2[u]
			c = u
		}
	}
	dfs(0, 0) //这样写代码就不是通用代码方法了，而是指定adj里面一定有节点0存在
	for j := p1[c]; j != -1; j = p1[j] {
		p = append(p, j)
	}
	for i, j := 0, len(p)-1; i < j; {
		p[i], p[j] = p[j], p[i]
		i++
		j--
	}
	p = append(p, c)
	for j := p2[c]; j != -1; j = p1[j] {
		p = append(p, j)
	}
	return
}
